package com.zklh.leetcode.top100.problem543;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 腐烂的橘子算法实现
 *
 * @version 1.0
 * @Author tongnan
 * @Date 2023/10/27
 */
public class Solution994 {
    public int orangesRotting(int[][] grid) {
        int[][] directs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
        int freshNumber = 0;
        Queue<int[]> badOranges = new LinkedList<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) {
                    freshNumber++;
                } else if (grid[i][j] == 2) {
                    badOranges.add(new int[]{i,j});
                }
            }
        }
        int minutes = 0;
        int maxI = grid.length-1;
        int maxJ = grid[0].length-1;
        while (badOranges.size() > 0 && freshNumber > 0) {
            minutes++;
            int badSize = badOranges.size();
            for (int i = 0; i < badSize; i++) {
                int[] badOrange = badOranges.poll();
                for (int[] direct : directs) {
                    int directI = badOrange[0] + direct[0];
                    int directJ = badOrange[1] + direct[1];
                    if (directI <= maxI && directI >= 0 && directJ <= maxJ && directJ >= 0) {
                        if (grid[directI][directJ] == 1) {
                            freshNumber--;
                            grid[directI][directJ] = 2;
                            badOranges.add(new int[]{directI, directJ});
                        }
                    }
                }
            }
        }

        if (freshNumber > 0) {
            return -1;
        }
        return minutes;
    }

    public static void main(String[] args) {
        Solution994 solution994 = new Solution994();
        // int[][] grid = {{2,1,1},{1,1,0},{0,1,1}};
        int[][] grid = {{0,2}};
        System.out.println(solution994.orangesRotting(grid));
    }
}